package 中等.滑动窗口;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/3sum-closest
 */
public class 最接近的三数之和_16 {

    public static void main(String[] args) {

        System.out.println(threeSumClosest(new int[]{-1, 2, 1, -4}, 1));

    }

    /**
     * 容易想到枚举 三层循环 a,b,c，容易超时，
     * 先枚举一层循环，a , 题目转换为，找出 b , c 最靠近 target-a
     * 剩下两层循环需要优化，先排序
     * 将 idxB=0 , idxC=nums.length-1
     * 如果  b+c >= target - a , idxC--，越靠近目标值，idxB++的话，
     * 使得 (b+c) 增大，偏离目标值
     * 如果 b+c <= target-a , idxB++ , (b+c) 增大 ,靠近目标值
     */
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];

        for (int idxA = 0; idxA < nums.length; idxA++) {
            int a = nums[idxA];
            int idxB = idxA + 1, idxC = nums.length - 1;
            while (idxB < idxC) {
                if (Math.abs(target - a - nums[idxB] - nums[idxC]) < target - ans) {
                    ans = a + nums[idxB] + nums[idxC];
                }
                if (nums[idxB] + nums[idxC] > target - a) {
                    idxC--;
                } else if (nums[idxB] + nums[idxC] < target - a) {
                    idxB++;
                } else {
                    // 三数之和直接等于目标值，最接近答案
                    return target;
                }
            }
        }

        return ans;
    }

}
